package cg.studio.algorithm.collection;

import java.util.Arrays;


public class Collections
{
  public static Node<Integer> mergeSortedList( Node<Integer> l1, Node<Integer> l2 )
  {
    //the node just previous of right node, it also is the tail of return list;
    Node<Integer> returnListTail =  null;
    Node<Integer> returnList = null;

    //find left1, right1 and left2, right2, form list [left1, preRight1) -> [left2, preRight2 ), 
    Node<Integer> left1 = l1;
    Node<Integer> right1 = null;
    Node<Integer> left2 = l2;

    while( left1 != null && left2 != null )
    {
      //left1 <= left2
      if( left1.getValue() > left2.getValue() )
      {
        Node<Integer> tmp = left1;
        left1 = left2;
        left2 = tmp;
      }
      if( returnList == null )
        returnList = left1;
      else
        returnListTail.setNext( left1 );
      
      //find right1 and preRight1
      right1 = left1;
      while( right1 != null && right1.getValue() <= left2.getValue() )
      {
        returnListTail = right1;
        right1 = right1.getNext();
      }
        
      //for next loo;
      left1 = left2;
      left2 = right1;
    }

    //only one list left, append to the return list;
    Node< Integer > leftOverList = ( left1 == null ) ? left2 : left1;
    if( returnListTail == null )
      return leftOverList;
    else
    {
      returnListTail.setNext( leftOverList );
      return returnList;
    }
  }
  
  public static Node<Integer> mergeSortedList_1( Node<Integer> l1, Node<Integer> l2 )
  {
    if( l1 == null )
      return l2;
    if( l2 == null )
      return l1;
    
    //find the head, and let l1 is the list same with head
    if( l1.getValue() < l2.getValue() )
    {
      return mergeSortListTo( l1, l2 );
    }
    else
    {
      return mergeSortListTo( l2, l1 );
    }
  }
  
  /**
   * merge list <another> to the list <list>
   * @param list the destination list, should not null.
   * @param another
   * @return
   */
  protected static Node<Integer> mergeSortListTo( Node<Integer> list, Node<Integer> another )
  {
    if( another == null )
      return list;
    
    Node<Integer> prev = list;
    Node<Integer> next = prev.getNext();
    
    while( another != null )
    {
      while( next != null && next.getValue() <= another.getValue() )
      {
        prev = next;
        next = prev.getNext();
      }
      // next.value > another.value, attach another to the prev
      prev.setNext( another );
      
      // the list of next become another
      another = next;
      
      next = prev.getNext();
    }
    
    return list;
  }
  
  /**
   * for an array of integer, all of the numbers are continuous duplicated except one
   * find that number and return.
   * for example: 1, 1, 2, 2, 3, 4, 4, 5, 5  should return 3
   * 
   * This problem can be solved by separate the array to 2 sub arrays.
   * the length of the array must be odd, so, divide the array in the middle. 
   * and then check the index of the middle number, if it is even( means the size of first sub array is even ),
   * then compare the number after that, else compare the number before that,
   * namely, keep the size of first sub-array even.
   * 
   * if the number we are looking is in the first sub array, then the compare should not equal: 1, 1, 3, 2, 2, 4, 4
   * if the number we are looking is one of the comparing number, the compare not equal
   * if the number is in second sub array, compare is equal: 1, 1, 2, 2, 3, 4, 4
   * 
   * the key point is:
   * all pair before single number start with even index and followed by odd index
   * all pair after single number start with odd index and followed by even index
   * 
   * @param elements
   * @return
   */
  public static int findSingleNumber( int[] elements )
  {
    if( elements == null || elements.length == 0 )
      throw new IllegalArgumentException( "elements should not null or empty." );
    return findSingleNumber( elements, 0, elements.length-1 );
  }
  
  public static int findSingleNumber( int[] elements, int start, int end )
  {
    if( start == end )
      return elements[start];
    int index = start + (end-start)/2;
    int element1 = elements[index];
    
    // the otherElement which opposite to element2. otherElement, element1, element2 or element2, element1, otherElement
    int element2;
    int otherElement;   
    if( index%2 == 0 )
    {
      //the length of first sub-array is even
      element2 = elements[ index+1 ];
      otherElement = elements[ index-1 ];
    }
    else
    {
      //the length of first sub-array is odd, make it even.
      element2 = elements[ index-1 ];
      otherElement = elements[ index+1 ];
    }
    if( element1 != element2 )
    {
      //element1 or element2 are the looking number or looking number is in first sub array
      if( element1 != otherElement )
      {
        //
        return element1;
      }
      
      end = index;
    }
    else
    {
      //the looking for element is in second sub-array
      start = index + 1 + (index+1)%2;
    }
    
    return findSingleNumber( elements, start, end );
  }
  
  
  /**
   * check if there are two integer which sum of them equals to <sum>
   * @param arr
   * @param sum
   * @return true if there are two integers which sum of them is <sum>
   * 
   */
  public static boolean hasSum( int[] arr, int sum )
  {
    Arrays.sort( arr );
    return hasSumOfOrderedArray( arr, sum );
  }
  
  /**
   * If there two elements a and b, and a+b=sum; so b-sum/2=sum/2-a ( assume b >=a )
   * namely 2b-sum=sum-2a( avoid float computing )
   * So, let each element double and then minus sum, 
   * and this problem transformed to find two number which sum are zero.
   * 
   * @param arr
   * @param sum
   * @return
   */
  public static boolean hasSumOfOrderedArray( int[] arr, int sum )
  {
    int leftIndex = 0; 
    int rightIndex = arr.length-1;
    while( rightIndex >= leftIndex )
    {
      int leftDiff = sum - arr[leftIndex]*2;
      int rightDiff = arr[rightIndex]*2 - sum;
      if( leftDiff == rightDiff )
      {
        //these two are the integers meet the requirement
        return true;
      }
      if( leftDiff > rightDiff )
        ++leftIndex;
      else
        --rightIndex;
    }
    return false;
  }
  
  public static void printArray( int[] arr, int startIndex, int length )
  {
    for( int i=startIndex; i<length; ++i )
      System.out.print( arr[i] + ", " );
  }
}
